function Tokenizer(){
}

function Entry(index, node, nodeOffset, nodeCount){
    this.index = index;
    this.node = node;
    this.nodeCount = nodeCount;
    this.nodeOffset = nodeOffset;
}

function Node(token){
    this.token = token;
    this.length = token.length;
    this.next = null;
}
Node.prototype.clip = function (startOffset, endOffset){
    this.token = this.token.slice(startOffset, endOffset);
    this.length = this.token.length;
};
Node.prototype.fill = function (node){
    this.token = node.token;
    this.length = node.length;
    this.next = node.next;
};
var _END_NODE = new Node('');

Tokenizer.prototype = {
    initTokenizer: function (splitNodeCount){
        this.$startNode = new Node({ type: 'eof', length: 0 });
        this.$splitNodeCount = splitNodeCount || 256;
        this.resetTokenizer();
    },
    resetTokenizer: function (){
        this.$startNode.next = _END_NODE;
        this.$entries = [new Entry(0, this.$startNode, 0, 1)];
        this.$cachedNode = null;
        this.$cachedNodeOffset = null;
    },
    findEntry: function (offset){
        var entries = this.$entries;
        var left = 0;
        var right = entries.length;
        while (left < right) {
            var middle = (left + right) >> 1;
            var middleEntry = entries[middle];
            if (offset < middleEntry.nodeOffset) {
                right = middle;
            } else {
                var nextEntry = entries[middle + 1];
                if (nextEntry == null || offset < nextEntry.nodeOffset) {
                    left = right = middle;
                } else if (offset === nextEntry.nodeOffset) {
                    left = right = middle + 1;
                } else {
                    left = middle + 1;
                }
            }
        }
        return entries[left];
    },
    findNode: function (offset, node, nodeOffset, findPartition){
        var entries = this.$entries;
        var entry = null;
        if (offset === 0) {
            return {
                entry: entries[0],
                node: entries[0].node,
                nodeOffset: 0,
                nodeIndex: 0
            };
        }
        if (node == null) {
            if (this.$cachedNode != null && !findPartition) {
                node = this.$cachedNode;
                nodeOffset = this.$cachedNodeOffset;
                if (offset < nodeOffset || (offset - nodeOffset) > Math.max(this.$splitNodeCount, node.length)) {
                    node = null;
                    this.$cachedNode = null;
                }
            }
            if (node == null) {
                entry = this.findEntry(offset);
                node = entry.node;
                nodeOffset = entry.nodeOffset;
            }
        }
        var nodeIndex = 0;
        while (node != null) {
            if (nodeOffset + node.length >= offset) {
                break;
            }
            nodeOffset += node.length;
            node = node.next;
            nodeIndex ++;
        }
        this.$cachedNode = node;
        this.$cachedNodeOffset = nodeOffset;
        return {
            entry: entry,
            node: node,
            nodeIndex: nodeIndex,
            nodeOffset: nodeOffset
        };
    },
    updateNodes: function (startOffset, endOffset, nodes){
        var r1 = this.findNode(startOffset, null, null, true);
        var startNode = r1.node;
        var startNodeOffset = r1.nodeOffset;
        var nodeIndex = r1.nodeIndex;
        var startEntry = r1.entry;
        var r2 = this.findNode(endOffset, startNode, startNodeOffset);
        var endNode = r2.node;
        var endNodeOffset = r2.nodeOffset;
        var endNodeIndex = nodeIndex + r2.nodeIndex;
        if (endOffset === endNodeOffset + endNode.length && endNode.next !== null) {
            endNode = endNode.next;
            endNodeOffset = endOffset;
            endNodeIndex ++;
        }
        var countDelta = nodeIndex - endNodeIndex + 1;
        var lengthDelta = nodes.length - (endOffset - startOffset);

        // 处理删除区间两端的node.
        if (startNode === endNode) {
            endNode = new Node(startNode.token);
            endNode.next = startNode.next;
            countDelta ++;
        }
        startNode.next = endNode;

        if (startNode.length) {
            startNode.clip(0, startOffset - startNodeOffset);
        }
        if (endNode.length) {
            endNode.clip(endOffset - endNodeOffset);
        }

        // 创建插入文本的nodes并链接他们.
        if (nodes.nodeCount) {
            var headNode = nodes.headNode;
            var tailNode = nodes.tailNode;
            startNode.next = headNode;
            tailNode.next = endNode;
            countDelta += nodes.nodeCount;
            if (this.eatNextNode(tailNode)) {
                countDelta --;
                // 更新endNode的引用, 使其始终指向最后一个node.
                endNode = tailNode;
            }
            if (this.eatNextNode(startNode)) {
                countDelta --;
                // 更新endNode的引用, 使其始终指向最后一个node.
                if (headNode === endNode) {
                    endNode = startNode;
                }
            }
        }
        if (startNode.length == 0 && startNode.next != null) {
            var nextNode = startNode.next;
            startNode.fill(nextNode);
            countDelta --;
            if (nextNode === endNode) {
                endNode = startNode;
            }
        }

        // 更新entries.
        var entries = this.$entries;
        var startEntryIndex = startEntry.index;
        var endEntryIndex = null;
        var entryEndNodeIndex = 0;
        for (var i=startEntryIndex; i<entries.length; i++) {
            var p = entries[i];
            if (endNodeIndex < entryEndNodeIndex + p.nodeCount) {
                endEntryIndex = i;
                break;
            }
            entryEndNodeIndex += p.nodeCount;
        }
        if (endEntryIndex === null) {
            endEntryIndex = entries.length - 1;
        }

        var insertEntryIndex = startEntryIndex + 1;
        var toBeDeletedEntryCount = endEntryIndex - startEntryIndex;
        var toInsertEntryCount = 0;
        var splitNodeCount = this.$splitNodeCount;
        var tidyNodeCount = splitNodeCount >> 1;

        var endEntry = entries[endEntryIndex];
        if (endEntry !== startEntry) {
            endEntry.node = endNode;
            // 因这个endPartition及之后的partitions都需要校正其offset, 所以放到后面一起处理.
            endEntry.nodeCount += countDelta;
            if (endEntry.nodeCount < tidyNodeCount) {
                // 这个时候startPartition和endPartition其实已经是连着的了. 所以可以这么操作.
                toBeDeletedEntryCount ++;
                startEntry.nodeCount += endEntry.nodeCount;
            }
        }

        var startEntryNodeCount = (startEntry.nodeCount = Math.max(0, startEntry.nodeCount + countDelta));
        var array = [insertEntryIndex, toBeDeletedEntryCount];
        if (startEntry.nodeCount > splitNodeCount) {
            toInsertEntryCount = Math.floor(startEntry.nodeCount / tidyNodeCount) - 1;
            startEntry.nodeCount = tidyNodeCount + (startEntryNodeCount % tidyNodeCount);
            var lastEntry = startEntry;
            for (var j=0; j<toInsertEntryCount; j++) {
                array.push(lastEntry = this.createNextEntry(lastEntry, tidyNodeCount));
            }
        }

        if (toBeDeletedEntryCount > 0 || toInsertEntryCount > 0) {
            entries.splice.apply(entries, array);
        }
        for (var k=insertEntryIndex+toInsertEntryCount; k<entries.length; k++) {
            var entry = entries[k];
            entry.index = k;
            entry.nodeOffset += lengthDelta;
        }
//        if (this.$cachedNode != null && endOffset <= this.$cachedNodeOffset) {
            this.$cachedNode = null;
//        }
        // 所有更新结束. ho~~~
    },
    updateTokens: function (startOffset, endOffset, data){
        this.updateNodes(startOffset, endOffset, this.createNodes(data));
    },
    createNextEntry: function (prevEntry, nodeCount){
        var node = prevEntry.node;
        var nodeOffset = prevEntry.nodeOffset;
        var index = prevEntry.index;
        var prevEntryNodeCount = prevEntry.nodeCount;
        for (var i=0; i<prevEntryNodeCount; i++) {
            nodeOffset += node.length;
            node = node.next;
        }
        return new Entry(index + 1, node, nodeOffset, nodeCount);
    },
    parseTokens: function (data, callback){

    },
    createNodes: function (data){
        var rootNode = new Node('');
        var lastNode = rootNode;
        var nodeCount = 0;
        this.parseTokens(data, function (token){
            var node = new Node(token);
            lastNode.next = node;
            lastNode = node;
            nodeCount ++;
        });
        return {
            headNode: rootNode.next,
            tailNode: lastNode,
            nodeCount: nodeCount,
            length: data.length
        };
    },
    createNodes1: function (tokens){
        var rootNode = new Node('');
        var lastNode = rootNode;
        var nodeCount = 0;
        var length = 0;
        for (var i=0; i<tokens.length; i++) {
            var node = new Node(tokens[i]);
            length += node.length;
            lastNode.next = node;
            lastNode = node;
            nodeCount ++;
        }
        return {
            headNode: rootNode.next,
            tailNode: lastNode,
            nodeCount: nodeCount,
            length: length
        };
    },
    eatNextNode: function (node){
        if (node !== this.$startNode && node.next !== null && node.next !== _END_NODE) {
            if (node.length === 0) {
                node.fill(node.next);
                return true;
            }
            var token = this.concatTwoTokens(node.token, node.next.token);
            if (token != null && token != node.token) {
                node.token = token;
                node.next = node.next.next;
                node.length = token.length;
                return true;
            }
        }
        return false;
    },
    concatTwoTokens: function (token, nextToken){
        return null;
    },
    walkNode: function (offset, callback){
        
    },
    walkTokens: function (startOffset, endOffset, callback){
        var r1 = this.findNode(startOffset);
        var r2 = this.findNode(endOffset);
        var startNode = r1.node;
        var startNodeStartOffset = r1.nodeOffset;
        var startNodeEndOffset = startNodeStartOffset + startNode.length;
        var endNode = r2.node;
        var endNodeStartOffset = r2.nodeOffset;
        var endNodeEndOffset = endNodeStartOffset + endNode.length;
        if (startNode === endNode) {
            if (endOffset - startOffset === startNode.length) {
                callback(startNode.token);
            } else if (endOffset > startOffset) {
                callback(startNode.token.slice(startOffset - startNodeStartOffset, endOffset - startNodeStartOffset));
            }
            return;
        }
        if (startOffset < startNodeEndOffset) {
            callback(startNode.token.slice(startOffset - startNodeStartOffset));
        }
        var node = startNode.next;
        while (node !== endNode) {
            callback(node.token);
            node = node.next;
        }
        if (endOffset > endNodeStartOffset) {
            callback(endNode.token.slice(0, endOffset - endNodeStartOffset));
        }
    }
};
